|
In game theory, a princess and monster game is a pursuit-evasion game played by two players in a region. The game was devised by Rufus Isaacs and published in his book ''Differential Games'' (1965) as follows. "The monster searches for the princess, the time required being the payoff. They are both in a totally dark room (of any shape), but they are each cognizant of its boundary. Capture means that the distance between the princess and the monster is within the capture radius, which is assumed to be small in comparison with the dimension of the room. The monster, supposed highly intelligent, moves at a known speed. We permit the princess full freedom of locomotion."〔R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, John Wiley & Sons, New York (1965), PP 349–350.〕 This game remained a well-known open problem until it was solved by Shmuel Gal in the late 1970s.〔S. Gal, SEARCH GAMES, Academic Press, New York (1980).〕 His optimal strategy for the princess is to move to a random location in the room and stay still for a time interval which is neither too short nor too long, before going to another (independent) random location and repeating the procedure.〔 The proposed optimal search strategy, for the monster, is based on subdividing the room into many narrow rectangles, picking a rectangle at random and searching it in some specific way, after some time picking another rectangle randomly and independently, and so on. Princess and monster games can be played on a pre-selected graph. (A possible simple graph is the circle, suggested by Isaacs as a stepping stone for the game in the region). It can be demonstrated that for any finite graph an optimal mixed search strategy exists that results in a finite payoff. This game has been solved by Steve Alpern and independently by Mikhail Zelikin only for the very simple graph consisting of a single loop (a circle). The value of the game on the unit interval (a graph with two nodes with a link in-between) has been estimated approximatively. This game looks simple but is quite complicated. Surprisingly, the 'obvious' search strategy of starting at one end (chosen at random) and 'sweeping' as fast as possible the whole interval is not optimal. This strategy guarantees 0.75 expected capture time. However, by utilising a more sophisticated mixed searcher and hider strategy, one can reduce the expected capture time by about 8.6%. Actually, this number would be quite close to the value of the game if someone was able to prove the optimality of the related strategy of the princess.〔S. Alpern, R. Fokkink, R. Lindelauf, and G. J. Olsder. (Numerical Approaches to the 'Princess and Monster' Game on the Interval. ) SIAM J. control and optimization 2008.〕〔L. Geupel. (The 'Princess and Monster' Game on an Interval. )〕 ==See also== *Search games *List of games in game theory 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Princess and monster game」の詳細全文を読む スポンサード リンク
|